//      suffix_array.cc
//      
//      Copyright 2012 tqlong <tqlong@espada>
//      
//      This program is free software; you can redistribute it and/or modify
//      it under the terms of the GNU General Public License as published by
//      the Free Software Foundation; either version 2 of the License, or
//      (at your option) any later version.
//      
//      This program is distributed in the hope that it will be useful,
//      but WITHOUT ANY WARRANTY; without even the implied warranty of
//      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//      GNU General Public License for more details.
//      
//      You should have received a copy of the GNU General Public License
//      along with this program; if not, write to the Free Software
//      Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
//      MA 02110-1301, USA.

#include "stl-helper.h"
#include "suffix_array.h"

std::string SuffixArray::temp = "";

SuffixArray::SuffixArray(std::string& s)
  : s_(s), order_(sz(s))
{
  build_array();
}

void SuffixArray::build_array() // naive suffix array build algorithm
{
  for (int i = 0; i < sz(order_); i++)
    order_[i] = i;
  std::sort(all(order_), *this);
}

bool SuffixArray::operator() (int i, int j) const
{
  return s_.substr(i).compare(s_.substr(j)) < 0;
}

int SuffixArray::count(const std::string& sub) const
{
  int p = sub.size();
  if (sub.compare(s_.substr(order_.front(), p)) < 0) return 0;
  if (sub.compare(s_.substr(order_.back(), p)) > 0 ) return 0;

  int left = find_left(sub); //MSG("left = " << left);
  int right = find_right(sub); //MSG("right = " << right);
  return (left <= right) ? right-left+1 : 0;
}

int SuffixArray::find_left(const std::string& sub) const
{
  int p = sub.size();
  int l = 0, r = sz(order_)-1; 
  while (l < r) {
    int m = (l+r)/2; //MSG("left m = " << m);
    int res = sub.compare(s_.substr(order_[m], p));
    if (res <= 0) r = m;
    else l = m+1;
  }
  return r;
}

int SuffixArray::find_right(const std::string& sub) const
{
  int p = sub.size();
  int l = 0, r = sz(order_)-1;
  while (l < r) {
    int m = (l+r)/2+1;// MSG("right m = " << m);
    int res = sub.compare(s_.substr(order_[m], p));
    if (res < 0) r = m-1;
    else l = m;
  }
  return l;
}

std::ostream& SuffixArray::print (std::ostream&o, bool isFile) const
{
  o << s_ << ENDL;
  BOOST_FOREACH(int i, order_)
    o << i << " "; 
  o << ENDL;
  return o;
}


SequencesSA::SequencesSA(Sequences& seqs)
  : seqs_(seqs)
{
  BOOST_FOREACH(std::string& s, seqs) {
    SuffixArray sa(s);
    this->pb(sa);
  }
}

int SequencesSA::count(const std::string& sub) const
{
  int s = 0;
  BOOST_FOREACH(const SuffixArray& sa, *this)
    s += sa.count(sub);
  return s;
}
